package com.cty._02_HighQualityCode._22_KthNodeFromEnd;

/**
 * @Auther: cty
 * @Date: 2020/7/8 10:26
 * @Description: 面试题22：链表中倒数第k个结点
 * 题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，
 * 本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，
 * 从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是
 * 值为4的结点。
 * @version: 1.0
 */
class ListNode {

    int value;
    ListNode next;

    public ListNode(){}

    public ListNode(int value){
        this.value = value;
    }

}  // end class

class LinkedList {
    private ListNode first;

    public LinkedList(){
        first = null;
    }

    private boolean isEmpty(){
        return first == null;
    }

    private void displayList(){
        ListNode current = first;
        while(current != null){
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    public void insertFirst(ListNode node){
        node.next = first;
        first = node;
    }

    public ListNode findKthToTail(int k){
        if(first==null || k<=0)
            return null;  // 链表空指针或k值不合法

        ListNode ptr1 = first;
        ListNode ptr2 = first;

        for(int i=1; i<k; i++) {  // ptr1先走k-1步
            if(ptr1.next == null)
                return null;  // 链表节点数小于k

            ptr1 = ptr1.next;
        }

        while(ptr1.next != null){  // ptr1和ptr2一起走直至ptr1为最后一个节点
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return ptr2;
    }  // end findKthToTail()

}  // end class
